package OfferLanQiaoBei.a_12届蓝桥真题;

import java.util.Scanner;
/*
给定序列 (a1,a2,⋅⋅⋅,an)=(1,2,⋅⋅⋅,n)，即 ai=i
小蓝将对这个序列进行 m 次操作，每次可能是将 a1,a2,⋅⋅⋅,aqi 降序排列，或者将 aqi,aqi+1,⋅⋅⋅,an 升序排列。
请求出操作完成后的序列。

输入格式
输入的第一行包含两个整数 n,m，分别表示序列的长度和操作次数。
接下来 m行描述对序列的操作，其中第 i 行包含两个整数 pi,qi 表示操作类型和参数。
当 pi=0 时，表示将 a1,a2,⋅⋅⋅,aqi 降序排列；当 pi=1 时，表示将 aqi,aqi+1,⋅⋅⋅,an 升序排列。

输出格式
输出一行，包含 n 个整数，相邻的整数之间使用一个空格分隔，表示操作完成后的序列。

数据范围
对于 30%的评测用例，n,m≤1000；
对于 60% 的评测用例，n,m≤5000；
对于所有评测用例，1≤n,m≤105，0≤pi≤1，1≤qi≤n

输入样例：

3 3
0 3
1 2
0 2

输出样例：

3 1 2

样例解释
	原数列为 (1,2,3)
	
	第 1步后为 (3,2,1)
	
	第 2步后为 (3,1,2)
	
	第 3步后为 (3,1,2)。
	与第 2 步操作后相同，因为前两个数已经是降序了。
 */
public class i双向排序test {
    static int N = 100010;
    static int n, m;
    static PII[] stk = new PII[N];
    static int[] ans = new int[N];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        int top = 0;//栈顶

        while (m -- > 0) {

            int p = sc.nextInt();
            int q = sc.nextInt();

            if (p == 0) {
                //求出连续操作的最长前缀
                while (top != 0 && stk[top].x == 0) q = Math.max(q, stk[top -- ].y);
                //优化三
                while (top >= 2 && stk[top - 1].y <= q) top -= 2;
                stk[ ++ top] = new PII(0, q);
            } else if (top != 0) {
                //求出连续操作的最长后缀
                while (top != 0 && stk[top].x == 1) q = Math.min(q, stk[top --].y);
                //优化三
                while (top >= 2 && stk[top - 1].y >= q) top -= 2;
                stk[ ++ top] = new PII(1, q);
            }
        }

        //k是递减变量，l为左边界，r为右边界
        int k = n, l = 1, r = n;
        for (int i = 1; i <= top; i ++ ) {
            if (stk[i].x == 0) {
                //若为前缀操作，则(stk[i].y, r]不用操作，直接填数
                while (r > stk[i].y && l <= r) ans[r -- ] = k --;
            } else {
                //若为后缀操作，则[l, stk[i].y)不用操作，直接填数
                while (l < stk[i].y && l <= r) ans[l ++ ] = k --;
            }
            if (l > r) break;
        }

        //若l < r, 表示中间还有些数没有填上，操作次数为奇数，则下一次操作为前缀操作
        if (top % 2 == 1) {
            while (l <= r) ans[l ++ ] = k --;
        } else {
            while (l <= r) ans[r -- ] = k --;
        }

        for (int i = 1; i <= n; i ++ ) System.out.print(ans[i] + " ");
    }

    private static class PII {
        int x;
        int y;
        public PII(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}
